googologywikiaorg-20200223-history
User blog:Edwin Shade/Understanding The Infinite
Among the many concepts of Googology, infinity plays a key role. This blog post seeks to teach anyone who finds themselves in the situation I was in when I was first introduced to Googology, when I had many questions, (and still do !), but had, (and still have !), difficulty in understanding the notations used because they were not broken down step by step, in the simplest way possible. Introduction to Cardinals and Ordinals Before we get into the nature of infinity, it would be good to distinguish between two types of numbers known as cardinals, and ordinals. These will be important. Cardinals are numbers which denote size or quantity, and are the type of numbers we are most familiar working with. For example, if you have 5 apple pies, the number 5 is a cardinal, since it refers to the amount of apple pies you have. Ordinals are numbers which denote order, or where in a list a given object is. This is why centuries are always referred to by a number that is one higher than you might expect, (e.g. calling 2000 the "21st century", and the 1600s the "17th century"). It is because you are counting in what century you are in, rather than by how many centuries have elapsed. A question: Suppose you are in a race and you pass the 2nd runner, which place are you ? If you said 1st, you would actually be wrong ! Surprisingly, the answer is 2nd, because in order to pass the 2nd runner you would have to have been the 3rd runner in the race, and consequently, passing the 2nd would only make you the 2nd runner. The tendency when you read that question was probably that since you were getting one closer to the front of the race, you could subtract 1 from 2 and get 1st place. You cannot always solve a problem using ordinals, (position), with cardinals, (quantity). You can now see why is it vital that you make a clear distinction between cardinals and ordinals. Cardinal and Ordinal Infinities Just as there are two types of numbers, there are two main types of infinity, cardinal infinites, and ordinal infinities. These, like their finite counterparts, are distinguished by size and order. Cardinal infinities are infinities which denotes the size of a set, or a collection of objects. As a brief primer on sets, all you need to know for now is that a set is any collection of objects enclosed in curly brackets, separated by comas. \{1, 2, 3, 4, ...\} is a set for example, and one that is familiar as the set of counting numbers. The size of a set has a special name, called cardinality, which refers to how many objects are in that set. The cardinality of the counting numbers, or \{1, 2, 3, 4, ...\} is given a special name, aleph-null, and is represented by the Hebrew letter Aleph with the subscript 0, or \aleph_0 . It was proven to be the smallest cardinal infinity by George Cantor, and consequently it is the first of the aleph-numbers, or cardinal infinities. Ordinal infinities are infinities which describe the order, or position, of an object in a sequence of objects. The first number after the sequence of counting numbers, or the sequence 1, 2, 3,... is given a special name, omega, and is represented by the Greek letter omega, or \omega . It is the first ordinal infinity, and has some interesting properties. If you subtract 1 from omega, it actually equals omega itself ! Since omega represents the limit of the counting numbers, if there were such an ordinal as \omega-1 , then that would be like asking what is the biggest number, and of course there is no biggest finite number ! There are infinitely many ordinal infinities. Ordinal Arithmetic A foray into the laws of ordinal arithmetic will be valuable, as they differ considerably from the laws of everyday arithmetic, which involves finite numbers. First, let us define two terms, which refer to two type of ordinals. They are limit-ordinals, and successor-ordinals. Limit-ordinals are ordinals which have no predecessor, so in other words, subtracting one does not make a difference. \omega is an example of a limit ordinal. A successor ordinal is an ordinal that has a predecessor, or is one more than the ordinal before it. \omega+3 is an example of a successor ordinal, as it's predecessor is \omega+3-1 or \omega+2 . \omega 2 is the limit of the sequence \omega, \omega+1, \omega+2, \omega+3,... , and hence is a limit ordinal due to it's lack of a predecessor. With that in mind, you can now understand the following rules of ordinal arithmetic. Greek letters represent ordinals. Rule 1: \alpha+0=\alpha This is straight forward enough, as adding 0 to an ordinal is the same as staying put and not moving from your position, which makes no difference. Rule 2: \alpha+(\beta+1)=(\alpha+\beta)+1 In words, an ordinal plus the successor of an ordinal is the successor of the two ordinals. Note how similar this is to the associative law of addition. Rule 3: \alpha+\beta is the limit of \alpha+\delta for all \delta<\beta , but only when \beta is a limit ordinal ! Rule 3 can be tricky to understand at first, so let's do an example of an addition of two ordinals, (one of which is a limit ordinal), namely, 6+\omega . By applying rule 3 to 6+\omega we can see it must equal the limit of 6+\delta , where \delta is an ordinal less than \omega . Trying successive values of \delta starting from 1, 6+\delta sums to 7, 8, 9, 10, ... and so forth. The limit of this sequence, (which should be familiar !), is of course \omega . So 6+\omega=\omega . It may seem odd, but it is due to the fact that \alpha+\beta does not always equal \beta+\alpha in ordinal arithmetic. Note that of the three rules we have established, no where is there a rule that preserves communitivity, therefore, ordinal arithemetic is said to be non-communitive. We have thus defined the rules for ordinal addition, but what if we wish to multiply two ordinals together ? The following rules apply, (again, Greek letters stand for ordinals). Rule 4: \alpha\cdot 0=0 In words, any ordinal multiplied by zero equals zero. Rule 5: \alpha(\beta+1)=(\alpha\cdot\beta)+\alpha In words, an ordinal multiplied by the successor of an ordinal is the same as the sum of the two ordinals plus the first. This bears much resemblance to the distributive law of multiplication. Rule 6: \alpha\cdot\beta is the limit of \alpha\cdot\delta for \delta<\beta , but only when \beta is a limit ordinal ! Similar to Rule 3, let's go through an example of ordinal multiplication, where a limit ordinal is involved, for example, (\omega+3)\cdot\omega . \omega+3 is a successor and \omega is a limit ordinal. By rule 6, we know (\omega+3)\cdot\omega ought to be the limit of (\omega+3)\cdot\delta , where \delta<\omega . So now let's plug in successive values for delta beginning with 1. (\omega+3)\cdot 1=\omega+3 (\omega+3)\cdot 2=(\omega+3)+(\omega+3)=((\omega+3)+\omega)+3=(\omega\cdot 2)+3 (\omega+3)\cdot 3=(\omega+3)+(\omega+3)+(\omega+3)=(\omega\cdot 3)+3 ... The limit of this sequence is \omega\cdot\omega , or \omega^2 , which is the answer to (\omega+3)\cdot\omega . Ordinals can of course be raised to the power of other ordinals, and so we must define ordinal exponentiation by the following rules. Rule 7: \alpha^0=1 An ordinal raised to the power of 0 is always 1. Rule 8: \alpha^{\beta+1}=(\alpha^{\beta})\cdot\alpha An ordinal to the power of the successor of an ordinal equals the first ordinal raised to the second, times the first. It is similar to, (but not the same as !), the exponent law x^{m+n}=x^m\cdot x^n . Rule 9: \alpha^{\beta} is the limit of \alpha^{\delta} for \delta<\beta , but only if \beta is a limit ordinal. To give an example of ordinal exponentiation would be tedious, but experiment around yourself, and you will get the hang of it. As for ordinal tetration, it is undefined, and thus all of ordinal arithmetic is governed by the above nine laws. To aid in memorization, you might think of the laws as being in three groups of three each, with the first law of each group being a base law, the second law being a case when successor ordinals are being used, and the third case applying to cases with limit ordinals. Cantor Normal Form and \epsilon_0 Now that we have defined ordinal addition, multiplication, and exponentiation, we are able to represent any ordinal of the form \cdot c_1}+ \cdot c_2}+...+ \cdot c_k} , where k is a a natural number, c_1, c_2, c_3,...,c_k are positive integers, (all the natural numbers excluding 0), and \beta_1, \beta_2, \beta_3,...,\beta_k are previously defined ordinal numbers such that \beta_1 >\beta_2 >\beta_3 >...>\beta_k\geq 0 . This has a special name known as Cantor Normal Form, and can express all ordinals that are expressible with finite application of addition, multiplication, and exponentiation upon the natural numbers and \omega . The ordinal known as "epsilon-nought" is the limit of Cantor Normal Form, and is equivalent to the smallest ordinal not representable in Cantor Normal Form, or \omega^{\omega^{\omega^{\omega^{\omega^{.^{.^{.}}}}}}} . This is conveniently notated as \epsilon_0 , which utilizes the Greek letter epsilon and a 0 in the subscript. BE CONTINUED Feel free by the way to ask any questions in the comments and I will answer them to the best of my ability. Category:Blog posts